package com.lw.leetcode.tree.b;

import com.lw.leetcode.linked.ListNode;

/**
 * Created with IntelliJ IDEA.
 * 148. 排序链表
 * 剑指 Offer II 077. 链表排序
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/26 9:41
 */
public class SortList {

    public static void main(String[] args) {

        SortList test = new SortList();
        ListNode instance6 = ListNode.getInstance6();
        ListNode listNode = test.sortList(instance6);
        System.out.println(listNode.str());
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode a = head;
        ListNode b = head.next;
        while (b != null && b.next != null) {
            a = a.next;
            b = b.next.next;
        }
        b = a.next;
        a.next = null;
        a = sortList(head);
        b = sortList(b);
        ListNode h = new ListNode(0);
        ListNode item = h;
        while (a != null && b != null) {
            if (a.val < b.val) {
                item.next = a;
                item = a;
                a = a.next;
                item.next = null;
            } else {
                item.next = b;
                item = b;
                b = b.next;
                item.next = null;
            }
        }
        if (a != null) {
            item.next = a;
        }
        if (b != null) {
            item.next = b;
        }
        return h.next;
    }

}
